package gold.digger;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;
import java.util.Stack;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC282 {
    public long startExecuteTime = System.currentTimeMillis();

    class Solution {
        List<String> ans = new ArrayList<>();
        String s;
        int n, t;

        public List<String> addOperators(String num, int target) {
            s = num;
            n = s.length();
            t = target;
            dfs(0, 0, 0, "");
            return ans;
        }

        void dfs(int u, long prev, long cur, String ss) {
            if (u == n) {
                if (cur == t) ans.add(ss);
                return;
            }
            for (int i = u; i < n; i++) {
                if (i != u && s.charAt(u) == '0') break;
                long next = Long.parseLong(s.substring(u, i + 1));
                if (u == 0) {
                    dfs(i + 1, next, next, "" + next);
                } else {
                    dfs(i + 1, next, cur + next, ss + "+" + next);
                    dfs(i + 1, -next, cur - next, ss + "-" + next);
                    long x = prev * next;
                    dfs(i + 1, x, cur - prev + x, ss + "*" + next);
                }
            }
        }
    }


    class Solution_Mine {

        List<String> res = new ArrayList<>();

        public List<String> addOperators(String num, int target) {
            addOperatorsBacktracking(num, target, new StringBuilder(), 0);
            return res;
        }

        public void addOperatorsBacktracking(String num, int target, StringBuilder curPath, int i) {
            if (i >= num.length() - 1) {
                // 当前已经是末尾位置，需要运算了
                curPath.append(num.substring(i, i + 1));
                try {
                    long curPathNum = calc(curPath.toString());
                    if (curPathNum == target) res.add(curPath.toString());
                    curPath.delete(curPath.length() - 1, curPath.length());
                } catch (Exception e) {
                    System.out.println("error!" + e.toString());
                }

                return;
            }

            // i 位置后面需要决定放置啥操作符
            curPath.append(num.substring(i, i + 1));

            // 对于i后面位置留空，前提是非（i位置为0&&i是数字前驱，即前面为操作符）
            // 1. 空置，啥也不放
            if (!(num.charAt(i) == '0' && curPath.length() >= 2 && !Character.isDigit(curPath.charAt(curPath.length() - 2))))
                addOperatorsBacktracking(num, target, curPath, i + 1);

            // 2. 放+
            curPath.append("+");
            addOperatorsBacktracking(num, target, curPath, i + 1);
            curPath.delete(curPath.length() - 1, curPath.length());

            // 3. 放-
            curPath.append("-");
            addOperatorsBacktracking(num, target, curPath, i + 1);
            curPath.delete(curPath.length() - 1, curPath.length());

            // 3. 放*
            curPath.append("*");
            addOperatorsBacktracking(num, target, curPath, i + 1);
            curPath.delete(curPath.length() - 1, curPath.length());
            curPath.delete(curPath.length() - 1, curPath.length());// 本身自己这个字符也需要删除回溯
        }

        public long calc(String numStr) throws Exception {
            Stack<Long> numStack = new Stack<>();
            // operator stack left with empty, default is always plus
            int i = 0;
            char prevOperator = ' ';
            while (i < numStr.length()) {
                int nextPos = i + 1;
                while (nextPos < numStr.length() && Character.isDigit(numStr.charAt(nextPos))) ++nextPos;
                // nextPos is an operator;
                if (nextPos >= numStr.length()) break;
                // current need to calc with prev num

                if (nextPos - i >= 2 && numStr.charAt(i) == '0') return Long.MIN_VALUE;
                if (prevOperator == '*') {
                    long prev = numStack.pop();
                    numStack.push(prev * Long.valueOf(numStr.substring(i, nextPos)));
                } else if (prevOperator == '-') {
                    numStack.push(-1 * Long.valueOf(numStr.substring(i, nextPos)));
                } else {
                    numStack.push(Long.valueOf(numStr.substring(i, nextPos)));
                }

                prevOperator = numStr.charAt(nextPos);
                i = nextPos + 1;
            }

            // process with end num
            if (numStr.length() - i >= 2 && numStr.charAt(i) == '0') return Long.MIN_VALUE;
            if (prevOperator == '*') {
                long prev = numStack.pop();
                numStack.push(prev * Long.valueOf(numStr.substring(i, numStr.length())));
            } else if (prevOperator == '-') {
                numStack.push(-1 * Long.valueOf(numStr.substring(i, numStr.length())));
            } else {
                numStack.push(Long.valueOf(numStr.substring(i, numStr.length())));
            }

            long sum = 0;
            while (!numStack.isEmpty()) sum += numStack.pop();
            return sum;
        }
    }


    public void run() {
        Solution solution = new Solution();
//        System.out.println(solution.addOperators("1000000009", 9));
//        System.out.println("\n\n\n\n-----\n\n\n");
//        System.out.println(new Solution_Mine().addOperators("1000000009", 9));
//        System.out.println(solution.addOperators("232", 8));
//        System.out.println(solution.addOperators("105", 5));
//        System.out.println(solution.addOperators("00", 0));
//        System.out.println(solution.addOperators("3456237490", 9191));


//        System.out.println(Math.pow(4, 9));

//        System.out.println(solution.calc("1+23-1-3"));
//        System.out.println(solution.calc("1*2*3-50"));
//        System.out.println(99999 * 99999);
//        System.out.println(Integer.MAX_VALUE);
//        System.out.println(Integer.valueOf("3456237490"));

//        Set<String> otherSo = new HashSet<>(new Solution().addOperators("1000000009", 9));
//        Set<String> mineSo = new HashSet<>(new Solution_Mine().addOperators("1000000009", 9));
//
//        for (String os : otherSo) {
//            if (!mineSo.contains(os)) {
//                System.out.println("os: " + os);
//            }
//        }

//        System.out.println(new Solution_Mine().addOperators("123", 6));
//        System.out.println(new Solution_Mine().addOperators("232", 8));
//        System.out.println(new Solution_Mine().addOperators("105", 5));
//        System.out.println(new Solution_Mine().addOperators("00", 0));
//        System.out.println(new Solution_Mine().addOperators("3456237490", 9191));
        System.out.println(new Solution_Mine().addOperators("2147483648", -2147483648));


    }

    public static void main(String[] args) throws Exception {
        LC282 an = new LC282();
        an.run();

        System.out.println("\ncurrent solution total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
